The invention relates to a method for the automatic generation, from a system or protocol specified as an FSM, of sequences of input signals, which are to be supplied to a system to be tested, together with the associated output signals which are to be received from the system to be tested and which serve to establish whether or not the implementation is in a particular state.
A useful introduction to the problems addressed by the present invention is provided in the U.S. Pat. No. 4,692,921 of AT&T, where it is stated that there has always been a need for the functioning of electronic systems to be tested and verified against the intended functioning. In the past, tests intended for this purpose were devised by the system designers who, in doing so, depended on their knowledge of the system design and the likely behaviour thereof. As VLSI (Very Large Scale Integration) progressed, this became more difficult. One of the causes is that there are no internal test points which can be approached to isolate faults. Another reason is that, in general, there are no repair possibilities. A further reason is that the design philosophy has changed from designs which attempt to limit the number of transistors to designs which intend to reduce the "real estate" and the input/output complexity.
The number of active elements in an integrated circuit (IC) amounts to hundreds of thousands, and is still increasing. The masks with which these ICs are produced are very expensive and it is therefore extremely important that the ICs fabricated therewith function according to their specifications. Another point is that during fabrication no defects must be introduced, such as active elements which stick on the value 1 or 0. Even more importantly, it must be possible for ICs containing such defects to be detected quickly and simply.
Hereinbelow, as in the said U.S. Patent, use will be made of the possibility to describe digital systems as "finite state machines" (FSM) which, in response to certain sequences of input signals, emit certain sequences of output signals. These are called finite state machines because, in contrast to analog systems, they can adopt only a limited number of internal states and jump from one state to another state ("state transition" or "edge") in response to one or more input signals. An FSM can therefore also be regarded as having been specified by its reaction to input signals (in the form of output signals). An FSM can be represented both in the form of a diagram and in the form of tables.
Said U.S. Patent discloses a method for developing test sequences for evaluating the design or the functioning of a digital system presented as an FSM. According to the method disclosed, the entire FSM is run through, and all the state transitions are tested. For each state transition, a test is developed which comprises a three-part test sequence. The first part is a sequence which puts the FSM into a first state. The second part, by supplying an input signal, causes a state transition from the first state to a second state. The third part is formed by a sequence which is unique for the second state and whose purpose is to check whether the implemented FSM has indeed reached the state desired (in accordance with the specified FSM). This part is therefore formed by a sequence of input signals together with the associated output signals, which is unique with respect to all the other states of the FSM and can serve as a "signature", as it were, for that state. The invention is in the field of the automatic generation, from a system or protocol specified as an FSM, of sequences of input signals, which are to be supplied to a system to be tested, together with the associated output signals which are to be received from the system to be tested and which serve to establish whether or not the implementation is in a particular state, in other words the generation of unique input/output sequences (UIO sequences), and is comparable to process step 1 in the said patent.
According to the known method for generating this type of sequences, the UIO sequences are generated via three intermediate steps. In the first intermediate step, a table is generated containing the "labels" of all state transitions and a designation of the "head" and the "tail" state(s) of each of those labels. In the second intermediate step, all the state transitions having a "null" input are identified, as well as all the state transitions whose tail state is identical to a head state of a state transition having a null input. Consecutive state transitions of this type then form a "meta" state transition. The meta state transitions and the remaining (non-null input) state transitions are incorporated in a second table. As a third step, this table is sorted according to state transition labels, and the labels which occur only once are marked. The labels are then sorted according to head state. The marked labels are unique. Finally, in a fourth step, the third step is repeated a number of times, resulting, generally, in a unique UIO sequence.
Generating UIO sequences in this manner have a number of drawbacks. Notably, the known method results in only one UIO sequence for a particular state. Furthermore, when carrying out the said fourth step of the known method, there is the risk that this ends up in an "infinite loop", namely if no UIO sequence can be found.
The method according to the present invention, in contrast, generates all the UIO sequences which are possible for a particular state (from which, incidentally, the shortest is preferably selected).